#include <stdio.h>

// 递归实现二分查找
int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) { // 递归终止条件：子数组为空
        return -1; // 没有找到目标值
    }

    int mid = left + (right - left) / 2; // 防止溢出的中间索引
    if (arr[mid] == target) {
        return mid; // 找到目标值，返回索引
    } else if (arr[mid] > target) {
        return binarySearch(arr, 0, mid - 1, target); // 在左半部分查找
    } else {
        return binarySearch(arr, mid + 1, right, target); // 在右半部分查找
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; // 已排序的数组
    int n = sizeof(arr) / sizeof(arr[0]);   // 数组长度
    int target = 5;                         // 要查找的值

    int result = binarySearch(arr, 0, n - 1, target); // 调用递归函数
    if (result != -1) {
        printf("元素 %d 在数组中的索引为 %d\n", target, result);
    } else {
        printf("元素 %d 不在数组中\n", target);
    }

    return 0;
}
